813F - Bipartite Checking - CodeForces Solution

#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector <pair<int,int> > vd[500005],vs[500005];
int t[100005],dist[100005],sz[100005],ras[100005],n,q;
pair<int,int> v[100005];
map<pair<int,int>,int> ma;
void query11(int st,int dr,int nod,int qa,int qb,pair<int,int> val)
{
    if (qa<=st&&dr<=qb)
    {
        vd[nod].push_back(val);
        return ;
    }
    int mij=(st+dr)/2;
    if (qa<=mij) query11(st,mij,nod*2,qa,qb,val);
    if (qb>mij) query11(mij+1,dr,nod*2+1,qa,qb,val);
}
pair<int,int> rep(int a,int sum)
{
    if (t[a]==a) return make_pair(a,sum);
    return rep(t[a],sum+dist[a]);
}
int united(int a,int b,int nod)
{
    pair<int,int> x=rep(a,0),y=rep(b,0);
    if (x.first!=y.first){
    vs[nod].push_back({x.first,y.first});
    if (sz[x.first]>sz[y.first]) swap(x,y);
    t[x.first]=y.first;
    sz[y.first]+=sz[x.first];
    if ((x.second+y.second)%2==0) dist[x.first]=1;
    return 0;
    }
    else
    {
        if ((x.second+y.second)%2==0) return 1;
        return 0;
    }
}
void ununite(int a,int b)
{
    if (t[a]!=b&&t[b]!=a) return ;
    if (t[b]==a) swap(a,b);
    t[a]=a;
    sz[b]-=sz[a];
    dist[a]=0;
}
void divd(int st,int dr,int nod)
{
    int ok=0;
    for (int i=0;i<vd[nod].size();++i)
    {
        ok=(ok|united(vd[nod][i].first,vd[nod][i].second,nod));
    }
    if (ok==0)
    {
        if (st==dr) {ras[st]=1;}
        else
        {
        int mij=(st+dr)/2;
        divd(st,mij,nod*2);
        divd(mij+1,dr,nod*2+1);
        }
    }
    for (int i=vs[nod].size()-1;i>=0;--i)
    {
        ununite(vs[nod][i].first,vs[nod][i].second);
    }

}
int main()
{
    cin>>n>>q;
    for (int i=1;i<=n;++i)
    {
        t[i]=i;
        sz[i]=1;
        dist[i]=0;

    }
    for (int i=1;i<=q;++i)
    {
        cin>>v[i].first>>v[i].second;
        if (ma[v[i]]==0) {ma[v[i]]=i;}
        else {query11(1,q,1,ma[v[i]],i-1,v[i]); ma[v[i]]=0;}
    }
    for (auto it:ma)
    {
        if (ma[it.first])
        {
            query11(1,q,1,it.second,q,it.first);
            ma[it.first]=0;
        }
    }
    divd(1,q,1);
    for (int i=1;i<=q;++i)
    {
        if (ras[i]==1) cout<<"YES";
        else cout<<"NO";
        cout<<'\n';
    }
    return 0;
}